class Solution {
public:
    int tribonacci(int n) {
        //      状态表示: dp[n]->第n个数
        //        初始化: 0,1,1
        //  状态转移方程: dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
        //        返回值: dp[n]
        //      空间优化:滚动数组->n0 n1 n2
        if(n==0)      return 0;
        if(n==1||n==2) return 1;
        int n0(0),n1(1),n2(1);
        for(int i=3;i<=n;i++){
            int n3=n0+n1+n2;
            n0=n1,n1=n2,n2=n3;
        }
        return n2;
    }
};